import heapq
from typing import List


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


def mergeKLists(lists: List[ListNode]) -> ListNode:
    heap = []
    h = res = ListNode(-1)
    for i, each in enumerate(lists):
        if each:
            heapq.heappush(heap, (each.val, i))
    while len(heap):
        t, i = heapq.heappop(heap)
        res.next = lists[i]
        res = res.next
        lists[i] = lists[i].next
        if lists[i]:
            heapq.heappush(heap, (lists[i].val, i))
    return h.next


a = ListNode(1)
a.next = ListNode(4)
a.next.next = ListNode(5)

b = ListNode(1)
b.next = ListNode(3)
b.next.next = ListNode(4)

c = ListNode(2)
c.next = ListNode(6)
d = mergeKLists([a, b, c])


while d:
    print(d.val)
    d = d.next
